package developer.算法.二叉树.对称二叉树;

/**
 * @author zhangyongkang
 * @time 2025/3/24 16:24
 * @description 给你一个二叉树的根节点 root ， 检查它是否轴对称。
 * <p>
 * 输入：root = [1,2,2,3,4,4,3]
 * 输出：true
 */
public class DuiChenErChaShu {

    /**
     * Definition for a binary tree node.
     * public class TreeNode {
     * int val;
     * TreeNode left;
     * TreeNode right;
     * TreeNode() {}
     * TreeNode(int val) { this.val = val; }
     * TreeNode(int val, TreeNode left, TreeNode right) {
     * this.val = val;
     * this.left = left;
     * this.right = right;
     * }
     * }
     */
    public static void main(String[] args) {
        Solution4 solution = new Solution4();
        TreeNode ta = new TreeNode(
                1,
                new TreeNode(2), new TreeNode(2)
        );
        TreeNode tb = new TreeNode(1, new TreeNode(2, new TreeNode(3, new TreeNode(5), new TreeNode()), new TreeNode(4)), new TreeNode(2, new TreeNode(3), new TreeNode(4)));
        boolean symmetric = solution.isSymmetric(
                tb
        );

        System.out.println(symmetric);

    }

    static class Solution4 {
        public boolean isSymmetric(TreeNode root) {
            return dfs(root.left, root.right);
        }

        private boolean dfs(TreeNode left, TreeNode right) {
            if (left == null && right == null) {
                return true;
            }
            if (left == null && right != null) {
                return false;
            }
            if (right == null && left != null) {
                return false;
            }
            boolean a = dfs(left.left, right.right);
            if (!a) {
                return false;
            }
            boolean b = dfs(left.right, right.left);
            if (!b) {
                return b;
            }
            return left.val == right.val;
        }


    }


    static class Solution {
        public boolean isSymmetric(TreeNode root) {
            if (root == null) return true;
            return isSymmetric(root.left, root.right);
        }

        public boolean isSymmetric(TreeNode left, TreeNode right) {
            if (left == null && right == null) return true;
            if (left == null && right != null) {
                return false;
            }
            if (left != null && right == null) {
                return false;
            }
            boolean symmetric = isSymmetric(left.left, right.right);
            if (!symmetric) return false;
            boolean b = left.val == right.val;
            if (!b) return false;
            boolean rightFlag = isSymmetric(left.right, right.left);
            if (!rightFlag) return false;
            return true;
        }


    }

    class SolutionOfficial {
        public boolean isSymmetric(TreeNode root) {
            return check(root.left, root.right);
        }

        public boolean check(TreeNode p, TreeNode q) {
            if (p == null && q == null) {
                return true;
            }
            if (p == null || q == null) {
                return false;
            }
            return p.val == q.val && check(p.left, q.right) && check(p.right, q.left);
        }
    }


    static class TreeNode {
        int val;
        TreeNode left;
        TreeNode right;

        TreeNode() {
        }

        TreeNode(int val) {
            this.val = val;
        }

        TreeNode(int val, TreeNode left, TreeNode right) {
            this.val = val;
            this.left = left;
            this.right = right;
        }
    }
}
